Subject: Returned mail: too many hops 18 (17 max): from <[email-masked]> via dgg1ig.mcimail.com, to <[email-masked]>

From: Mail Delivery Subsystem <[email-masked]>
Date: Thu, 15 May 1997 07:01:31 GMT

The original message was received at Thu, 15 May 1997 07:01:31 GMT
from dgg1ig.mcimail.com [166.40.135.79]

   ----- Transcript of session follows -----
554 too many hops 18 (17 max): from <[email-masked]> via dgg1ig.mcimail.com, to <[email-masked]>

   ----- Original message follows -----

Subject: Returned mail: too many hops 18 (17 max): from <[email-masked]> via dgg2ig.mcimail.com, to <[email-masked]>
From: qosr <[email-masked]>
To: qosr <[email-masked]>, postmaster <[email-masked]>
Date: Thu, 15 May 1997 01:57:54 -0500 (EST)

The original message was received at Wed, 14 May 1997 21:31:41 GMT
from dgg2ig.mcimail.com [166.40.135.80]

   ----- Transcript of session follows -----
554 too many hops 18 (17 max): from <[email-masked]> via dgg2ig.mcimail.com, to <[email-masked]>

   ----- Original message follows -----

Subject: Re: Can't you make your mailer attach appropriate subject, Ariel?
From: qosr <[email-masked]>
To: mohta <[email-masked]>
Cc: qosr <[email-masked]>, chotipat <[email-masked]>, qma <[email-masked]>, guerin <[email-masked]>, ougw <[email-masked]>, prz <[email-masked]>, ariel <[email-masked]>
Date: Wed, 14 May 1997 16:27:52 -0500 (EST)

Masataka,

I have the feeling that the discussion is going nowhere. Nevertheless,
I'll make a last attempt at addressing the confusions that seem to 
remain based on the statements in your note.

 > >  M>Can you show me the reference to [Go96] again?
 > >  M>
 >A> Oops, I now see that in my first note I referenced it as [GuOr] - sorry
 >A> for that. Here are the references:
 >A> 
 >A> [GuOr] Roch Guerin and Ariel Orda, "QoS-based routing in Networks with
 >A>        Inaccurate Information: Theory and Algorithms". IBM Report,
 >A>        July 96. (Available through http://www.watson.ibm.com:8080/.)

 M> Thank you. I may look at it if I have time.

In view of this statement, I don't see the point of continuing the discussion
on issues for which you were referred to that work. However, here are some
specific comments.
 
 >>  M>What, do you mean, "uncertainity" is?
 >>  M>
 >A> We defined it in [GuOr], but it essentially amounts to the fact that
 >A> you cannot be sure that the appropriate resources are available, even
 >A> when the advertised information states they are.

 M>Then, inaccuracy does not mean uncertainity.
 M>
 M>Inaccuracy means uncertainity only when you aggregate inappropriately.

It is hard to discuss the terminology of [GuOr] before you read it.

 >>  M>With moderate underestimation of resource, we can "certainly" find
 >>  M>a path without cranking back operations.
 >>  M>
 >>  M>Then, there is a possibility that a certain path can not be found,
 >>  M>becasue of underestimated aggregated resource, which is not a
 >>  M>problem.
 >>  M>
 >>  M>Of course, there can be transient uncertainity even if we don't
 >>  M>aggregate. But, simple retry can get around it.
 >>  M>

 >A> Certainly, but in general it is desirable to avoid as much as possible
 >A> retries or any other form of crankback.

 M>
 M> Sure. So, just have pessimistic aggregattion.

... and often waste too much resources. May not be a good solution
in general.

 M> And, you miss my last point. That is, transient uncertainity is
 M> unavoidable as long as there is packet transmission delay or
 M> packet loss possibility, both of which is quite common in the
 M> real networks, which is totally unrelated to aggregation.

The fact that transient uncertainty is unavoidable is yet another reason
that motivated our work [GuOr]. Again, it is hard to discuss it as long 
as you don't read it.

 > A> Hence, you would like your
 > A> (path selection) algorithm to not only try to pick the "cheapest" path
 > A> that meets your constraint, but also do so in a fashion that *minimizes*
 > A> the likelihood you'll have to retry (or crankback).

 M> That's a requirement with self contradiction.
 M>
 M> If we choose "cheapest", there is practically no room to "*minimizes*"
 M> something else.

Let me rephrase for you: minimizing the likelihood etc. is an important
objective that one may want to address.

 > >   >A> (2) In each execution, record the shortest path (w.r.t. the "constant > >   >A> delays" metric of each link) for each possible hop count.
 > >  M>
 > >  M>No. The Bellman-Ford algorithm finds a best path with no more,
 > >  M>hop count than, but not necessarily equal to, the current hop
 > >  M>limit.
 > >  M>
 >A> What you say about the BF algorithm is true,
 M> 
 M> What I say about Qingming's result is true.

Please have a look a few lines above, and verify that in *your* message
it is written "The Bellman-Ford algorithm". My comment, placed just
below it, referred to it. Also, this was in the context of explaining
to you my algorithm, not Qingming's.  

 >A> but has no bearing on the result.

 M> Wrong, becasue the complexity is not the same.

The complexity *is* the same:
The (main) algorithm I proposed used the *standard* BF, for each of the
O(M) rate values, just as in the former approach. The complexity is thus 
still O(M*H) for each BF execution (M=number of links, H=maximal number 
of hops), and O(M^2*H) for all O(M) rate values.
The same holds for the other, modified BF that I mentioned, that is,
it also maintains the same complexity (see the following).

 >A> Actually, even if it had, it would have only required a mild modification
 >A> of the BF algorithm to "fix" this.

 M> I know.
 M>
 M> The problem is that, now, you must compute modified-BF "for all the hop
 M> count" in addition to "for all the bandwidth".
 M>
 M> Thus, the complexity is now different.

No: the modified-BF is executed *just once*, and while it is executed, just 
as with the standard BF, it has one iteration per each hop count. The 
complexity of both the standard and modified BF is, as I mentioned, O(M*H). 

 M> It is, still, theoretically interesting slightly that the result is still
 M> polynominal.
 M>
 M> If you are interested in writing a research paper on it, feel free to
 M> do so, as long as I am included as a co-author.

I am not interested in writing anything on "it", since "it" is evidently 
less efficient than what I specified and was trying to explain to you
in my former notes. 

 >A> Now, let's come back to the fact that the algorithm described in the previous 
 >A> note does not require the above modification to the BF algorithm, i.e.,
 >A> it generates the correct path using a standard BF algorithm. For that 
 >A> purpose, let's consider the form of the Guaranteed Service [GS96] 
 >A> end-to-end delay bound. In the expression for the GS bound, decreasing 
 >A> the hop count while keeping all other parameters, i.e., rate/bandwidth and 
 >A> propagation delays, constant, results in a lower bound.

 M> As I repeatedly said, Qingming's algorithm is fine to find the
 M> existence of a path. But, it is no good to find the path.
 M> 
 M> The problem is that, after we find a path we should decrease the
 M> required bandwidth, which affect the queueing delay, which then
 M> affect the end-to-end delay in non-uniform fashion.
 M> 
 M> That is, your assumption that "keeping all other parameters" is wrong.

I was not making any "assumption" here. Let me rephrase for you: the
end-to-end delay bound is a function of several arguments, one of them
is the hop count, with respect to which the function is non-decreasing.

Please look again at the structure of the end to end delay bound (see, 
e.g., [GuOr] or Qingming's paper) and at the algorithm I specified and 
explained in my previous notes, and check that my algorithm does solve 
the problem, with no additional complexity, i.e.: it finds, in O(M^2*H)
steps, the path p and bandwidth b such that the end to end delay constraint 
is obeyed and such that b is the minimal possible bandwidth for meeting 
that constraint, on any path. (As I also explained, the algorithm can be 
modified in order to accommodate a more general cost function.) In particular,
note that, in my algorithm, the link metric used in the BF is just the 
"constant" delay component (i.e., the component which does not depend on the 
rate/bandwidth): d_l according to the notation of [GuOr], L_{max}/C_l + prop_l 
according to that of Qingming's paper); this is different than in Qingming's 
algorithm, in which the respective metric included also the component 
L_{max}/rate. 

Ariel